import queue
import copy

# ===CODE===

class DAG:
    def __init__(self):
        self._in = {}   # {node_name : set}
        self._out = {}  # {node_name : set}
        self.zero_in = set()

    def set_edge(self, from_name, to_name):
        '''设置一条边的信息，from指向to，to依赖from'''
        # 保证每个key都存在
        if from_name not in self._out:
            self._out[from_name] = set()
        if from_name not in self._in:
            self._in[from_name] = set()
        if to_name not in self._in:
            self._in[to_name] = set()
        if to_name not in self._out:
            self._out[to_name] = set()
        # 设置边的关系
        self._out[from_name].add(to_name)
        self._in[to_name].add(from_name)
        # 更新入度为0的结点
        if len(self._in[from_name]) == 0:
            self.zero_in.add(from_name)
        if to_name in self.zero_in:
            self.zero_in.remove(to_name)

    def set_point(self, name):
        if name not in self._in:
            self._in[name] = set()
        if name not in self._out:
            self._out[name] = set()
        self.zero_in.add(name)

    def get_topology_sort(self):
        in_nodes = copy.deepcopy(self._in)
        out_nodes = copy.deepcopy(self._out)
        zero_in = list(self.zero_in)
        ret = []
        while len(zero_in) > 0:
            # 取出一个入度为0的结点
            name = zero_in.pop()
            ret.append(name)
            # 删除当前结点
            for child_name in out_nodes[name]:
                in_nodes[child_name].remove(name)
                # 记录入度为0的子节点
                if len(in_nodes[child_name]) == 0:
                    zero_in.append(child_name)
            out_nodes.pop(name)
            in_nodes.pop(name)
        return ret
                


    def get_dep_nodes(self, node_name):
        # 以node_name作为起始结点，在self._in中遍历一遍
        ret = set()
        q = queue.Queue()        
        q.put(node_name)
        while q.empty() == False:
            node_name = q.get()
            for pre_node_name in self._in[node_name]:
                q.put(pre_node_name)
                ret.add(pre_node_name)
        return ret  

    def pop_zero_in_deg_node(self):
        pass

